package zigzagLevelOrder

import "container/list"

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

/**
给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

广度搜索
双向链表
*/

func zigzagLevelOrder(root *TreeNode) [][]int {
	queue := list.New()
	var ans [][]int
	if root == nil {
		return ans
	}
	queue.PushBack(root)
	ans = append(ans, []int{root.Val})
	index := true
	for queue.Len() > 0 {
		// 每层的结点数
		num := queue.Len()
		var v []int
		// 因为每层遍历的顺序不一样，所以另外定义一个链表保存下一层结点的顺序
		tempList := list.New()
		// 外层的每次循环都是一层
		// 每次循环做两件事：1、遍历下一次层节点 2、将下一层节点以相反的顺序保存入队
		for i := 0; i < num; i++ {
			var e *list.Element
			if index {
				// 从表头取，此层是反序，下一层是正序
				// 正序则用pushBack
				e = queue.Front()
				queue.Remove(e)
				node := e.Value.(*TreeNode)
				// 反序则优先访问右侧子节点
				if node.Right != nil {
					v = append(v, node.Right.Val)
					queue.PushBack(node.Right)
				}
				if node.Left != nil {
					v = append(v, node.Left.Val)
					queue.PushBack(node.Left)
				}
			} else {
				//从表尾取，此层是正序，下一次是反序
				//反序则用pushFront
				e = queue.Back()
				queue.Remove(e)
				node := e.Value.(*TreeNode)
				//正序则优先访问左侧子节点
				if node.Left != nil {
					v = append(v, node.Left.Val)
					queue.PushFront(node.Left)
				}
				if node.Right != nil {
					v = append(v, node.Right.Val)
					queue.PushFront(node.Right)
				}
			}
		}
		if len(v) > 0 {
			ans = append(ans, v)
			queue.PushBackList(tempList)
		}
		index = !index
	}
	return ans
}
